#include "BreakAndRefillGroupAlgorithm.h"
#include "Helpers.h"
#include "GreedyFillMaximalGroupAlgorithm.h"
#include "GreedyFillGroupAlgorithm.h"
#include <math.h>

using std::set;
using std::vector;

/*****************************************************************************/
//
// author: Mor Weiss
//
// BreakAndRefillGroupAlgorithm
// Algorithm for improving an independent group by breaking and refilling it:
// 1. Keep in the group only groupPercentToKeep percent first vertices of the 
// group and return all the others to the graph. 
// 2. Iterations trying to replace the initial group with better ones:
// (GreedyFillMaximalGroupAlgorithm::Fill).
// 3. Return the best (biggest) group found over all the iterations.
//
// Input: Graph G=(V,E)
// independent Group S to be filled
// integer size: required size of the group (if negative then there is no size limitation)
// integer iterations: number of iterations to run before returning the best option;
// double groupPercentToKeep: percentage of initail group to keep when breaking the group
// (we keep the first vertices).
// double startCouplesPercent, stopCouplesPercent, integer couplesNum:  parameters passed
// to GreedyFillMaximalGroupAlgorithm::Fill
//
// Output: The graph G & the group S after filling S.
//
/*****************************************************************************/

//-----------------------------------------------------------------------------
// BreakAndRefill method: The method that does the actual refilling of a group
// dir: The vertex directory the provided group & graph use. If NULL then it is
// the static vertex directory
// Note: This method may throw an std::bad_alloc exception due to memory allocation memory
// when initiating a copy of the vertex directory.
//-----------------------------------------------------------------------------
Group& BreakAndRefillGroupAlgorithm::BreakAndRefill(Graph &graph, Group &group, 
		int iterations, double groupPercentToKeep, double startCouplesPercent, 
		double stopCouplesPercent, int couplesNum, VertexDirectory* directory)
{
	Logger::LogMessage("Running break and refill on "+group.PrintName());

	// create a VertexDirectory copy and use it in this run (so we don't influance the state of the graph)
	VertexDirectory* dir;
	if (directory == NULL)
	{	// use static vertex directory to create the copy
		dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	}
	else
	{	// use the procided vertex directory to create the copy
		dir = new VertexDirectory(directory->GetWorkingCopyVertices());
	}
	
	// all operations are done on a copy of the graph, since we remove neighbours that should appear
	// in the graph when the algorithm finishes running
	Graph* tempGraph = graph.CloneFromDirectory(dir);
	if (tempGraph == NULL)	//memory allocation failed
	{
		delete dir;
		Logger::LogMessage("ERROR: Unable to create graph in BreakAndRefillGroupAlgorithm::BreakAndRefill. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create graph in BreakAndRefillGroupAlgorithm::BreakAndRefill. Algorithm didn't run.");		
	}
	// all operations are done on a copy of the group	
	Group* brokenGroup;
	try
	{
		brokenGroup = new Group(group, dir);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		delete tempGraph;
		delete dir;
		Logger::LogMessage("ERROR: Unable to create group in BreakAndRefillGroupAlgorithm::BreakAndRefill. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create group in BreakAndRefillGroupAlgorithm::BreakAndRefill. Algorithm didn't run.");
	}
	
	// thrownVertices will hold the vertices we removed from the original group, to get 
	// broken group
	list<Vertex*> thrownVertices;
	// break the group..
	Logger::LogMessage("Breaking group");
	brokenGroup = group.BreakGroup(groupPercentToKeep, &thrownVertices, dir);
	if (brokenGroup == NULL)	//memory allocation failed
	{
		delete tempGraph;
		delete dir;
		Logger::LogMessage("ERROR: unable to break group in BreakAndRefillGroupAlgorithm::BreakAndRefill. The algorithm didn't run.");
		throw new GraphColoringException("ERROR: unable to break group in BreakAndRefillGroupAlgorithm::BreakAndRefill. The algorithm didn't run.");
	}
	// ..and return the vertices we removed to the graph
	tempGraph->AddVertices(thrownVertices);
	// Fill the group with no limitation on the group size
	*brokenGroup = GreedyFillMaximalGroupAlgorithm::Fill(*tempGraph, *brokenGroup, iterations,
		startCouplesPercent, stopCouplesPercent, couplesNum, dir);

	// check if we were able to improve the initial group
	if (group.Size() < brokenGroup->Size())
	{
		// update the graph & the group
		Algorithms::UpdateGraphAndGroupFromCopies(graph, group, *brokenGroup);
	}
	// free allocated memory
	delete tempGraph;
	delete brokenGroup;
	delete dir;
	return group;
}




